# 冒泡排序
def bubbleSort(a: list[int]) -> list[int]: 
    bound, exchange = 0, len(a) - 1
    while exchange != 0:
        bound = exchange
        exchange = 0
        for i in range(bound):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                exchange = i
    return a

# 选择排序
def selectSort(a: list[int]) -> list[int]:
    for i in range(0, len(a) - 1):
        index = i
        for j in range(i + 1, len(a)):
            if a[j] < a[index]:
                index = j
        if index != i:
            a[i], a[index] = a[index], a[i]
    return a

# 插入排序
def insertSort(a: list[int]) -> list[int]: 
    for i in range(1, len(a)):     # 从第 2 个记录开始执行
        t, j = a[i], i - 1         # 将待插入元素暂存于变量 t 
        while j >= 0 and t < a[j]: # 搜索插入位置，注意不要越界
            a[j + 1] = a[j]        # 记录后移
            j -= 1
        a[j + 1] = t               # 完成 t 的插入操作
    return a

# 完整代码参见2.4.1章节代码实现，此处略

# 归并排序
def mergeSort(a: list[int], left: int, right: int) -> list[int]:
    
    # 边界条件：没有元素或 1 个元素直接返回
    if left > right: return []
    if (left == right): return [a[left]]

    # 划分并求解子问题
    mid = left + (right - left) // 2
    a1 = mergeSort(a, left, mid)
    a2 = mergeSort(a, mid + 1, right)

    # 合并：注意这里需要开一个新的数组然后才进行数据复制
    c, i1, i2 = [], 0, 0
    while i1 < len(a1) and i2 < len(a2): 
        if a1[i1] <= a2[i2]:
            c.append(a1[i1])
            i1 += 1
        else:
            c.append(a2[i2])
            i2 += 1

    # 不要忘记对子数组的剩余部分进行合并
    if i1 < len(a1):
        c += a1[i1:]
    elif i2 < len(a2):
        c += a2[i2:]

    return c

# main中调用，注意传参（前后代码略）
# a = mergeSort(a, 0, len(a) - 1)

# 完整代码参见2.4.1章节代码实现，此处略

# 此处先演示一个递归一行完成快排的代码(SimpleQuickSort=sqs)
# 注意因为没有原地排序，实际上这段代码并没有发挥快速排序的优势
# 只是通过一行代码演示快速排序的核心算法，帮助读者理解
def sqs(a: list[int]) -> list[int]:
    return sqs([x for x in a[1:] if x <= a[0]]) + [a[0]] + sqs([x for x in a if x > a[0]]) if a else []

# 以下是完整的快速排序实现，采用原地排序的方式

#（快速排序核心算法）对 a[p..r] 进行划分操作
def partition(a: list[int], p: int, r: int) -> int:
    pivot = a[p] # 选定轴值
    i, j = p, r  # 初始化左右指针
    while i < j:
        while i < j and pivot <= a[j]:
            j -= 1
        if i < j:
            a[i], a[j] = a[j], a[i]
            i += 1
        while i < j and pivot >= a[i]:
            i += 1
        if i < j: 
            a[i], a[j] = a[j], a[i]
            j -= 1
    return i

# 快速排序
def quickSort(a: list[int], p: int, r: int):
    if p < r:
        q = partition(a, p, r) # 划分，并返回轴值在数组中的位置
        quickSort(a, p, q - 1) # 递归求解左子数组
        quickSort(a, q + 1, r) # 递归求解右子数组

# main中调用，注意传参（前后代码略）
# quickSort(a, 0, len(a) - 1)

# main (本章节后续部分相同)
a = [ 49, 12, 54, 96, 26, 37, 48, 64 ]
print('排序前:', a)
quickSort(a, 0, len(a) - 1)
print('排序后:', a)
